﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0193_FinalPrices : IAlgorithm
    {
        // 1475. 商品折扣后的最终价格

        // 给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
        // 商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，
        // 其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
        // 请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

        // 提示：
        //  1 <= prices.length <= 500
        //  1 <= prices[i] <= 10^3

        public void Test()
        {
            // 算法参数定义
            var p = new int[] { 8, 4, 6, 2, 3 };
            // 算法执行与打印
            foreach (var item in FinalPrices(p))
            {
                Console.Write(item + "");
            }
        }

        // 算法
        public int[] FinalPrices(int[] prices)
        {
            int n = prices.Length;
            int[] ans = new int[n];
            Stack<int> stack = new Stack<int>();
            for (int i = n - 1; i >= 0; i--)
            {
                while (stack.Count > 0 && stack.Peek() > prices[i])
                    stack.Pop();
                ans[i] = stack.Count == 0 ? prices[i] : prices[i] - stack.Peek();
                stack.Push(prices[i]);
            }
            return ans;
        }
    }
}
